package algorithm.leetcode.I401to600;

import algorithm.leetcode.TreeNode;

/**
 * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
 * 也就是二叉树里面两个节点的最远距离
 * tricky的地方在于,递归函数是返回树的深度,但是树的深度不等于直径,左子树高度+右子树高度 才是
 */

public class Q543 {
    int ans;

    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);
        return ans-1;
    }

    // 核心是这个递推关系
    private int depth(TreeNode node) {
        if (node == null) return 0;

        int leftDepth = depth(node.left);
        int rightDepth = depth(node.right);
        ans = Math.max(ans, leftDepth+rightDepth+1);
        return Math.max(leftDepth, rightDepth)+1;
    }

}
